﻿using System;
using System.Collections.Generic;

namespace ProblemsSet
{
    public class Problem_60 : BaseProblem
    {
        public override object GetResult()
        {
            return GetAnswer();
        }

        private static long GetAnswer()
        {
            const int cnt = 5;
            
            var primes = MathLogic.GetPrimeList(10000, true);
            var res = new List<List<long>>();
            FormeList(ref primes, 0, new List<long>(), cnt, ref res);
            if (res.Count == 0) return -1;
            long sum = 0;
            foreach (var l in res[0])
            {
                sum += l;
            }
            return sum;
        }

        private static void FormeList(ref List<long> primes, int startIndex, List<long> current, int count, ref List<List<long>> result)
        {
            if (result.Count > 0) return;
            for (var i = startIndex + 1; i < primes.Count - count + current.Count + 1; i++)
            {
                bool ex = true;
                foreach (var l in current)
                {
                    if (!MathLogic.IsPrimesRemarkable(l, primes[i]))
                    {
                        ex = false;
                        break;
                    }
                }
                if (!ex) continue;

                var tmp = new List<long>(current);
                tmp.Add(primes[i]);
                if (tmp.Count == count)
                {
                    result.Add(tmp);
                    continue;
                }
                FormeList(ref primes, i, tmp, count, ref result);
            }

        }

        public override string Problem
        {
            get
            {
                return @"The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return 26033;
            }
        }

    }
}
